package java_thinking.unit_17;

import java.util.*;

/**
 * @Desc:   必看：https://blog.csdn.net/chenssy/article/details/26668941
 *      1.基于红黑树（Red-Black list）的 NavigableMap 实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的
 *        Comparator 进行排序，具体取决于使用的构造方法
 *
 *      2.键值对是有序的
 *
 *      3.底层数据结构是
 *          static final class Entry<K,V> implements Map.Entry<K,V> {
 *              K key;
 *              V value;
 *              Entry<K,V> left;
 *              Entry<K,V> right;
 *              Entry<K,V> parent;
 *              boolean color = BLACK;
 *          }
 *
 *      4.遍历是从最左子树开始的，遵循LDR中序遍历原则进行遍历：见entrySet()
 *          L-D-R。具体细节如下：
 *              a. 空节点，没有后继
 *              b. 有右子树的节点，后继就是右子树的“最左节点”
 *              c. 无右子树的节点，后继就是该节点所在左子树的第一个祖先节点
 *
 *      5.注意，如果要正确实现 Map 接口，则有序映射所保持的顺序（无论是否明确提供了比较器）都必须与 equals 一致。（关于与 equals 一致
 *        的精确定义，请参阅 Comparable 或 Comparator）。这是因为 Map 接口是按照 equals 操作定义的，但有序映射使用它的 compareTo
 *        （或 compare）方法对所有键进行比较，因此从有序映射的观点来看，此方法认为相等的两个键就是相等的。即使排序与 equals 不一致，
 *        有序映射的行为仍然是 定义良好的，只不过没有遵守 Map 接口的常规协定。
 *
 *     6.TreeMap key如果是对象时，如果不实现 Comparable 接口,会抛异常;
 *       这是因为在调用put()方法时，会将传入的元素转化成 Comparable 类型对象，所以当你传入的元素没有实现Comparable接口时，
 *       就无法转换，会报:"java.lang.ClassCastException: com.jiaboyan.collection.map.SortedTest cannot be cast to java.lang.Comparable"异常；
 *
 *     7.TreeMap key如果是null,会抛空指针异常NullPointerException；
 *
 * @author: cww
 * @DateTime: 2019/5/8 8:44
 */

public class TreeMapTheory {
    final String getString() {
        return "ww";
    }
    public static void main(String[] args) {
        Map<Integer,String> map = new TreeMap<>();
        map.put(12,"C_value");
        map.put(1,"A_value");
        map.put(9,"A_value");
        map.put(2,"A_value");
        map.put(0,"A_value");
        map.put(11,"A_value");
        map.put(7,"A_value");
        map.put(19,"A_value");
        map.put(4,"A_value");
        map.put(15,"A_value");
        map.put(18,"A_value");
        map.put(5,"A_value");
        map.put(14,"A_value");
        map.put(13,"A_value");
        map.put(10,"A_value");
        map.put(16,"A_value");
        map.put(6,"A_value");
        map.put(3,"A_value");
        map.put(8,"A_value");
        map.put(17,"A_value");
        map.remove(18);
        Set<Map.Entry<Integer,String>>  entrySet = map.entrySet();
        Iterator<Map.Entry<Integer,String>> iterator = entrySet.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        Queue<Integer> queue = new PriorityQueue<>();
        System.out.println("end");
    }
}
